#include "stdio.h"
#include "stdlib.h"


// 合并区间，leetcode题目地址：https://leetcode-cn.com/problems/merge-intervals/

int intervals[4][2] = {{1, 3}, {8, 10}, {2, 6}, {15, 18}};

int compFunc(const void *a, const void *b)
{
    // 这里的 a、b 为二重指针， (int **)a 代表将a强制类型转换为 二重整形指针；
    //  *(int **)a  代表将上面的转换结果，取指针指向的值，运算结果即为一重指针（相当于二维数组中的一维）

    int ret;

    int valuea = (*(int **)a)[0];
    int valueb = (*(int **)b)[0];

    if (valuea < valueb)
    {
        ret = -1;
    }
    else
    {
        ret = 1;
    }
    return ret;
}
int max(int x, int y)
{
    return x < y ? y : x;
}
int **merge(int **intervals, int intervalsSize, int *intervalsColSize, int *returnSize, int **returnColumnSizes)
{

    if (intervalsSize == 0)
    {
        *returnSize = 0;
        return NULL;
    }
    qsort(intervals, intervalsSize, sizeof(intervals[0]), compFunc);

    int **res = (int **)malloc(intervalsSize * sizeof(int *));

    // 此时的res长度为 一重指针的指针长度，也就是8， 而res[0]即为一重指针的长度，也是8，因此二重指针的元素长度不能用 sizeof(res)/sizeof(res[0]) 来获取
    // 这里的数组长度因为是不确定的，所以需要通过malloc(num*size)或者 calloc(num,size)来动态分配空间
    returnColumnSizes = (int **)malloc(intervalsSize * sizeof(int));

    int idx = -1;
    int i;

    for (i = 0; i < intervalsSize; i++)
    {

        // 如果当前元素的起始元素值 > 结果中 结尾元素的 终止值，代表没有重叠，直接将当前元素加入到结果数组
        if (idx == -1 || intervals[i][0] > res[idx][1])
        {
            idx++;
            // 同样的道理，由于是动态的元素，占据的空间也需要动态分配
            res[idx] = (int *)malloc(2 * sizeof(int));
            // 同上
            returnColumnSizes[idx] = (int *)malloc(sizeof(int));

            // 这个返回值在这里，实际上没啥意义，就是定义每个列的宽度，固定为2，因为这个是区间形式，只有上限和下线
            (*returnColumnSizes)[idx] = 2;

            // res[idx][0] = intervals[i][0];
            // res[idx][1] = intervals[i][1];
            res[idx] = intervals[i];
        }
        else
        {
            // 否则，将当前元素的 终止值与结果元素的终止值取较大者赋值给 结果元素的终止值
            res[idx][1] = max(res[idx][1], intervals[i][1]);
        }
    }

    // 返回值的最终长度，这里方便理解，其实idx可以直接使用 (*returnSize) 代替
    *returnSize = idx + 1;

    return res;
}

int main()
{

    int size = sizeof(intervals) / sizeof(intervals[0]);

    int *intervalsColSize;
    int *returnSize;
    int **returnColumnSizes;

    int *p[4];

    int i;
    for (i = 0; i < size; i++)
    {
        p[i] = intervals[i];
    }

    printf("合并前结果为：\n");
    for (int i = 0; i < size; i++)
    {
        printf("[%d, %d],", intervals[i][0], intervals[i][1]);
    }
    printf("\n");

    int **result = merge(p, size, intervalsColSize, returnSize, returnColumnSizes);

    printf("合并后结果为：\n");
    int j;
    for (j = 0; j < *returnSize; j++)
    {
        printf("[%d, %d],", result[j][0], result[j][1]);
    }
    printf("\n");

    return 0;
}